/*************************************************************************
 * File Name:    Triangle.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 21 Sep 2013 04:10:52 PM CST
 * 
 * Description:  
 *
 | --------------------------------------------------------------------------
 | Triangle
 |
 | Given a triangle, find the minimum path sum from top to bottom. 
 | Each step you may move to adjacent numbers on the row below.
 |
 | For example, given the following triangle
 |
 | [
 |      [2],
 |     [3,4],
 |    [6,5,7],
 |   [4,1,8,3]
 | ]
 | The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
 |
 | Note:
 | Bonus point if you are able to do this using only O(n) extra space,
 | where n is the total number of rows in the triangle.
 | -------------------------------------------------------------------------
 |
 ************************************************************************/

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int n = triangle.size();
        if (n == 0) return 0;

        vector<int> ans(triangle[n - 1].begin(), triangle[n - 1].end());

        for (int i = n - 2; i >= 0; --i) {
            for (size_t j = 0; j < triangle[i].size(); ++j) {
                ans[j] = triangle[i][j] + min(ans[j], ans[j + 1]);
            }
        }
        return ans[0];
    }
};

int
main(int argc, char *argv[])
{
    vector<vector<int> > triangle;

    return 0;
}

